from random import *
import string

#class to contain a graph, list of edges and list of vertices
class Graph:
    slots = ["edges","vertices","name"]

    def __init__(self, v, e, n = "unnamed"):
        self.edges = e
        self.vertices = v
        self.name = n
#write
def write(filename, g):
    f = open(filename, "w")
    f.write(str(len(g.vertices))+" "+str(len(g.edges))+"\n")
    f.write("\n")
    for e in g.edges:
        f.write(str(e[0]) + " " + str(e[1]) + "\n")
    f.close()

#load 
def load(filename):
    f=open(filename)
    first=True
    e=[]
    for line in f:
        if first:
            vert=int(string.split(line," ")[0])
            v=[x for x in range(vert)]
            edge=int(string.split(line," ")[1])
            first=False
        else:
            if len(line)>0 and len(string.split(line," "))>1:
                e.append((int(string.split(line," ")[0]),int(string.strip(string.split(line, " ")[1],"\n"))))
    return Graph(v,e,filename)    
            

#generates a wheel of n vertices on the perimeter
def wgen(v_count):
    v = [x for x in range(v_count)]
    e = []
    for i in range(v_count-1):
        e.append((i,i+1))
    e.append((v_count-1, 0))
    vf = v_count
    for i in v:
        e.append((i,vf))

    return Graph(v,e,''.join(["wheel (",str(v_count),")"]))

#generates a line of n vertices
def lgen(v_count):
    v = [x for x in range(v_count)]
    e = []
    for i in range(v_count-1):
        e.append((i,i+1))

    return Graph(v,e,''.join(["line (",str(v_count),")"]))

#generates a cycle of n vertices
def cgen(v_count):
    v = [x for x in range(v_count)]
    e = []
    for i in range(v_count-1):
        e.append((i,i+1))
    e.append((v_count-1, 0))

    return Graph(v,e,''.join(["cycle (",str(v_count),")"]))

#generates a tree on n vertices
#it does this by generating all possible edges (i.e. Kn) and running the
#kruskal algorithm on the graph
def tgen(v_count):
    v = [x for x in range(v_count)]
    e = []
    temp_elist = []
    temp_vlist = []

    for i in range(v_count):
        for j in range (i+1,v_count):
            temp_elist.append((i,j))

    initial = randint(0,len(temp_elist)-1)
    edge = temp_elist[initial]
    e.append(edge)
    temp_elist.remove(edge)
    temp_vlist.append(edge[0])
    temp_vlist.append(edge[1])
    while len(e) != len(v)-1:
        i = randint(0,len(temp_elist)-1)
        edge = temp_elist[i]
        if (temp_vlist.count(edge[0]) > 0) ^ (temp_vlist.count(edge[1]) > 0):
            e.append(edge)
            temp_elist.remove(edge)
            if temp_vlist.count(edge[0]) == 0:
                temp_vlist.append(edge[0])
            if temp_vlist.count(edge[1]) == 0:
                temp_vlist.append(edge[1])

    return Graph(v,e,''.join(["tree (",str(v_count),")"]))
    

#returns a random graph on the specified number of vertices
def graphgen(v_count):
    v = [x for x in range(v_count)]
    e = []
    for i in range(v_count):
        for j in range (i,v_count):
            if i != j and random() > 0.5:
                e.append((i,j))

    return Graph(v,e,''.join(["random (",str(v_count),")"]))

#returns a complete bi-partite graph of the given sizes
def kkgraphgen(k1, k2):
    v1 = [x for x in range(k1) ]
    v2 = [x for x in range(k1, k2 + k1)]
    e = []
    for i in v1:
        for j in v2:
            e.append((i,j))
    v1.extend(v2)
    return Graph(v1,e,''.join(["bipartite (",str(k1),",",str(k2),")"]))

#returns a complete graph of the given size
def kgraphgen(v_count):
    v = [x for x in range(v_count)]
    e = []
    for i in range(v_count):
        for j in range (i,v_count):
            if i != j:
                e.append((i,j)) 
    return Graph(v,e,''.join(["Complete (",str(v_count),")"]))

#this is our predicate for determining if a set is a valid matching
#it looks for vertices that occur multiple times in an edge set        
def isMatching(e_set):
    v = []
    for e in e_set:
        if v.count(e[0]) == 0:
            v.append(e[0])           
        else:
            return False

        if v.count(e[1]) == 0:
            v.append(e[1])           
        else:
            return False
    return True

